package leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by baoyunfeng on 2019/8/18.
 */
public class CourseSchedule {

    public static void main(String args[]) {

        CourseSchedule courseSchedule = new CourseSchedule();
        courseSchedule.canFinish(2,new int[2][2]);
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int edges[][] = new int[numCourses][numCourses];
        for (int[] edge : prerequisites) {
            edges[edge[0]][edge[1]] = 1;
        }

        List topoRes = new ArrayList();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            for (int j = 0; j < numCourses; j++) {
                if (edges[i][j] > 0) {
                    inDegree[j]++;
                }
            }
        }

        Deque<Integer> deque = new LinkedList();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                deque.offer(i);
            }
        }

        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int i = 0; i < numCourses; i++) {
                if (edges[curr][i] > 0) {
                    inDegree[i]--;
                    if (inDegree[i] == 0) {
                        if(topoRes.contains(i)){
                            return false;
                        }
                        deque.offer(i);
                    }
                }
            }
        }

        return topoRes.size() == numCourses ? true : false;
    }


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
